DC/LC analysis of Keccak-f[50]
Linear cryptanalysis

1 trails of length 2 read and checked.
1 trails of length 3 read and checked.
1 trails of length 4 read and checked.
1 trails of length 5 read and checked.
1 trails of length 6 read and checked.
Minimum weight: 8
       1 trails of weight  8
       1 trails of weight 16
       1 trails of weight 30
       1 trails of weight 40
       1 trails of weight 52

Showing the trails up to weight 52 (in no particular order).

2-round linear trail of total weight 8
* Profile related to χ:
Propagation weights:    4   4
Active rows:            2   2
* Profile related to θ:
Gaps:      3   0
Kernel:    N   k
Previous round would have weight at least 22
Round 0 (weight 4) after previous χ, then before θ of gap 3, then before χ (2 active rows):
X..X.   XXX.X  |  XX.XX   .X...  |  .....   ..X..
..XX.   XX.X.  |  XX.XX   XXX..  |  .....   X....
.X+X.   XXX.X  |  XX+XX   .XX..  |  ..+..   .....
XXXXX   ...XX  |  XX.XX   .XX..  |  .....   .....
.XX.X   X.XX.  |  XX.XX   .XX..  |  .....   .....
                  OO-OO   OO---
Round 1 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   ..X..  |  .....   .....  |  .....   .....
.....   X....  |  .....   .....  |  .....   .....
..+..   .....  |  ..+X.   .....  |  ..+X.   .....
.....   .....  |  .....   .....  |  .....   .....
.....   .....  |  ...X.   .....  |  ...X.   .....
                  -----   -----

3-round linear trail of total weight 16
* Profile related to χ:
Propagation weights:    6   6   4
Active rows:            3   3   2
* Profile related to θ:
Gaps:      3   0   0
Kernel:    N   k   k
Previous round would have weight at least 20
Round 0 (weight 6) after previous χ, then before θ of gap 3, then before χ (3 active rows):
..X..   .XXXX  |  X.XX.   ..XX.  |  .....   ....X
XXX.X   X...X  |  X.XX.   ..XXX  |  .....   .....
..XX.   X.XX.  |  X.XX.   ..XX.  |  ..+..   ....X
XX...   XX.X.  |  X..X.   ..XXX  |  ..X..   .....
XX.XX   ...XX  |  X.XX.   ..XXX  |  .....   .....
                  O--O-   --OOO
Round 1 (weight 6) after previous χ, then before θ of gap 0, then before χ (3 active rows):
.....   ....X  |  X...X   .....  |  X...X   .....
.....   .....  |  .....   .....  |  .....   .....
..+..   X...X  |  ..+.X   .....  |  ..+.X   .....
..X..   .....  |  .....   .....  |  .....   .....
.....   .....  |  X....   .....  |  X....   .....
                  -----   -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
....X   .....  |  .....   X...X  |  .....   X...X
.....   .....  |  .....   .....  |  .....   .....
X.+.X   .....  |  ..+..   .....  |  ..+..   .....
.....   .....  |  .....   .....  |  .....   .....
X....   .....  |  .....   X...X  |  .....   X...X
                  -----   -----

4-round linear trail of total weight 30
* Profile related to χ:
Propagation weights:    6   6   4  14
Active rows:            3   3   2   6
* Profile related to θ:
Gaps:      3   0   0   1
Kernel:    N   k   k   N
Previous round would have weight at least 20
Round 0 (weight 6) after previous χ, then before θ of gap 3, then before χ (3 active rows):
..X..   .XXXX  |  X.XX.   ..XX.  |  .....   ....X
XXX.X   X...X  |  X.XX.   ..XXX  |  .....   .....
..XX.   X.XX.  |  X.XX.   ..XX.  |  ..+..   ....X
XX...   XX.X.  |  X..X.   ..XXX  |  ..X..   .....
XX.XX   ...XX  |  X.XX.   ..XXX  |  .....   .....
                  O--O-   --OOO
Round 1 (weight 6) after previous χ, then before θ of gap 0, then before χ (3 active rows):
.....   ....X  |  X...X   .....  |  X...X   .....
.....   .....  |  .....   .....  |  .....   .....
..+..   X...X  |  ..+.X   .....  |  ..+.X   .....
..X..   .....  |  .....   .....  |  .....   .....
.....   .....  |  X....   .....  |  X....   .....
                  -----   -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
....X   .....  |  .....   X...X  |  .....   X...X
.....   .....  |  .....   .....  |  .....   .....
X.+.X   .....  |  ..+..   .....  |  ..+..   .....
.....   .....  |  .....   .....  |  .....   .....
X....   .....  |  .....   X...X  |  .....   X...X
                  -----   -----
Round 3 (weight 14) after previous χ, then before θ of gap 1, then before χ (6 active rows):
.....   ....X  |  X....   ...X.  |  X....   .XXX.
.....   .....  |  .....   .....  |  .....   .XX..
..+..   .....  |  ..+..   .....  |  ..+..   .XX..
.....   .....  |  .....   .....  |  .....   .XX..
.....   ....X  |  .....   .....  |  .....   .XX..
                  O----   ---O-

5-round linear trail of total weight 40
* Profile related to χ:
Propagation weights:    8  12  10   6   4
Active rows:            4   5   3   3   2
* Profile related to θ:
Gaps:      2   0   1   0   0
Kernel:    N   k   N   k   k
Previous round would have weight at least 18
Round 0 (weight 8) after previous χ, then before θ of gap 2, then before χ (4 active rows):
X..XX   .....  |  ....X   X...X  |  .X...   .....
.X.X.   .XX..  |  .X..X   X....  |  .....   ....X
XX+.X   ..X.X  |  .X+.X   X.X.X  |  ..+..   ..X..
..XX.   ..X..  |  XX..X   X...X  |  X....   .....
XX...   XXX..  |  .X..X   X...X  |  .....   .....
                  O---O   O-O--
Round 1 (weight 12) after previous χ, then before θ of gap 0, then before χ (5 active rows):
.X.X.   .....  |  ..X..   .....  |  ..X..   .....
.....   .X..X  |  ....X   .....  |  ....X   .....
..+..   ..X..  |  ..+..   ..X..  |  ..+..   ..X..
X....   .....  |  ..X.X   .....  |  ..X.X   .....
.....   .....  |  .....   ..X..  |  .....   ..X..
                  -----   -----
Round 2 (weight 10) after previous χ, then before θ of gap 1, then before χ (3 active rows):
..X..   .....  |  ....X   ..XX.  |  ....X   .....
XX..X   .....  |  .....   ..XX.  |  .....   .....
..+..   ..XXX  |  .X+.X   ..XX.  |  .X+.X   .....
X.X..   .....  |  .....   ....X  |  .....   ..XXX
.....   ..XXX  |  .....   ..XX.  |  .....   .....
                  -O---   ----O
Round 3 (weight 6) after previous χ, then before θ of gap 0, then before χ (3 active rows):
....X   .....  |  .....   X...X  |  .....   X...X
.....   .....  |  .....   .....  |  .....   .....
X.+.X   .....  |  ..+..   ....X  |  ..+..   ....X
.....   ..X..  |  .....   .....  |  .....   .....
.....   .....  |  .....   X....  |  .....   X....
                  -----   -----
Round 4 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   ....X  |  X...X   .....  |  X...X   .....
.....   .....  |  .....   .....  |  .....   .....
..+..   X...X  |  ..+..   .....  |  ..+..   .....
.....   .....  |  .....   .....  |  .....   .....
.....   X....  |  X...X   .....  |  X...X   .....
                  -----   -----

6-round linear trail of total weight 52
* Profile related to χ:
Propagation weights:    4   4  14  18   6   6
Active rows:            2   2   6   6   3   3
* Profile related to θ:
Gaps:      2   0   1   1   1   0
Kernel:    N   k   N   N   N   k
Previous round would have weight at least 20
Round 0 (weight 4) after previous χ, then before θ of gap 2, then before χ (2 active rows):
.X..X   ...XX  |  X.X..   XX..X  |  .....   .X...
.XX..   ..X.X  |  X.X..   X...X  |  .....   .....
X.X.X   X....  |  X.X..   X...X  |  ..+..   .....
...XX   X.XX.  |  ..X..   X...X  |  X....   .....
X..X.   .X...  |  X.X..   X...X  |  .....   .....
                  --O--   OO--O
Round 1 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   .X...  |  .....   .....  |  .....   .....
.....   .....  |  .....   .....  |  .....   .....
..+..   .....  |  ..+..   .....  |  ..+..   .....
X....   .....  |  .....   ..X..  |  .....   ..X..
.....   .....  |  .....   ..X..  |  .....   ..X..
                  -----   -----
Round 2 (weight 14) after previous χ, then before θ of gap 1, then before χ (6 active rows):
.....   .....  |  .....   .....  |  .....   ..XX.
.....   .....  |  .....   .....  |  .....   ..XX.
..+..   .....  |  .X+..   ....X  |  .X+..   ..XXX
.....   ..X..  |  .....   .....  |  .....   ..XX.
.....   ..X..  |  .....   .....  |  .....   ..XX.
                  -O---   ----O
Round 3 (weight 18) after previous χ, then before θ of gap 1, then before χ (6 active rows):
.....   ..X.X  |  X....   .....  |  ...X.   .....
.....   X.XX.  |  X..X.   .XX..  |  .....   .XX..
.X+X.   ..X..  |  .X+X.   X.X.X  |  XX+..   X.X.X
.....   X.XX.  |  .X...   .....  |  XX.X.   .....
.....   X.XX.  |  ..XXX   .....  |  X.X.X   .....
                  --OOO   OO--O
Round 4 (weight 6) after previous χ, then before θ of gap 1, then before χ (3 active rows):
...X.   .....  |  ....X   .X...  |  .....   .....
.....   .X.X.  |  ....X   XX...  |  .....   X....
X.+..   XX..X  |  ..+.X   .X...  |  ..+..   .....
..XXX   .....  |  ....X   .X...  |  .....   .....
..X..   .....  |  X....   X....  |  X...X   XX...
                  O----   -----
Round 5 (weight 6) after previous χ, then before θ of gap 0, then before χ (3 active rows):
.....   .....  |  ...X.   .....  |  ...X.   .....
.....   XX...  |  .....   .....  |  .....   .....
..+..   .....  |  ..+..   .....  |  ..+..   .....
.....   .....  |  ....X   .....  |  ....X   .....
....X   X....  |  ...XX   .....  |  ...XX   .....
                  -----   -----

